package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Administrator
 * @date 2020/7/28 11:21
 */
public class IntegerOperation {
    /**
     * 数字序列中某一位的数字
     * 数字以0123456789101112131415…的格式序列化到一个字符序列中。
     * 在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
     * 请写一个函数，求任意第n位对应的数字。
     */
    @Test
    public void findNthDigit() {
        Assert.assertEquals(9, findNthDigit(36542));
    }

    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) { // 1.
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; // 2.
        return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
    }

    /**
     * a>=b
     * 最大公约数
     *
     * @param a
     * @param b
     * @return
     */
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    /**
     * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。
     * 求按从小到大的顺序的第 n 个丑数。
     */
    @Test
    public void nthUglyNumber() {
        Assert.assertEquals(12, nthUglyNumber(10));
        Assert.assertEquals(15, nthUglyNumber(11));
    }

    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if (dp[i] == n2) a++;
            if (dp[i] == n3) b++;
            if (dp[i] == n5) c++;
        }
        return dp[n - 1];
    }

    /**
     * 两数相除
     * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
     * 返回被除数 dividend 除以除数 divisor 得到的商。
     * 整数除法的结果应当截去（truncate）其小数部分，
     * 例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
     */
    @Test
    public void divide() {
        Assert.assertEquals(3, divide(10, 3));
        Assert.assertEquals(-3, divide(10, -3));
        Assert.assertEquals(-2, divide(7, -3));
    }

    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;

        boolean k = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
        int result = 0;
        dividend = -Math.abs(dividend);
        divisor = -Math.abs(divisor);
        while (dividend <= divisor) {
            int temp = divisor;
            int c = 1;
            while (dividend - temp <= temp) {
                temp = temp << 1;
                c = c << 1;
            }
            dividend -= temp;
            result += c;
        }
        return k ? result : -result;
    }

    /**
     * 复原IP地址
     * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
     * 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
     */
    @Test
    public void restoreIpAddresses() {
        Assert.assertArrayEquals(new String[]{"255.255.11.135", "255.255.111.35"}, restoreIpAddresses("25525511135").toArray());
        Assert.assertArrayEquals(new String[]{"0.10.0.10", "0.100.1.0"}, restoreIpAddresses("010010").toArray());
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        restoreIpAddresses(s, new int[5], 1, res);
        return res;
    }

    public void restoreIpAddresses(String s, int[] index, int size, List<String> res) {
        if (size == 5) {
            if (index[index.length - 1] == s.length()) {
                StringBuilder stringBuilder = new StringBuilder();
                stringBuilder.append(s);
                for (int i = index.length - 2; i >= 1; i--) {
                    stringBuilder.insert(index[i], '.');
                }
                res.add(stringBuilder.toString());
            }
            return;
        }
        for (int i = index[size - 1] + 1; i <= s.length(); i++) {
            int current = Integer.valueOf(s.substring(index[size - 1], i));
            if (255 < current || (s.charAt(index[size - 1]) == '0' && i - index[size - 1] > 1)) {
                break;
            }
            index[size] = i;
            restoreIpAddresses(s, index, size + 1, res);
        }
    }

}
